package edu.dali.algorithm.graph;

import java.util.*;


// Dijkstra 复杂度是O(ElogE)
public class DijkstraByPriorityQuene {

    private WeightedGraph G;

    //原点s到某个顶点的相应的最短路径
    private int[] dis;
    //原点
    private int s;
    // 对应的那些顶点已经确定了最小值
    private boolean[] visited;

    //结点路径，记录最短路径来自于哪个结点
    private int[] pre;

    private class Node implements Comparable<Node> {
        public int v; // 顶点
        public int dis; // 距离

        public Node(int v , int dis) {
            this.v = v;
            this.dis = dis;
        }

        @Override
        public int compareTo(Node another) {
            return dis - another.dis;
        }
    }

    public DijkstraByPriorityQuene(WeightedGraph G, int s){
        this.G = G;
        //验证原点是合法的
        G.validateVertex(s);
        //开辟空间 有多少个顶点就有多个元素
        dis = new int[G.V()];
        //将每个点的距离赋值为无穷大
        Arrays.fill(dis , Integer.MAX_VALUE);
        pre = new int[G.V()];
        //原点距离自己的距离为0
        dis[s] = 0;
        //原点的上一个顶点，就是他自己
        pre[s] = 0;
        //开辟空间 默认为false
        visited = new boolean[G.V()];

        // 复杂度log级别
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        // 优先队列中加入原点
        pq.add(new Node(s , 0));
        // 队列中的数据不为空就继续循环
        while(!pq.isEmpty()) {
            // 取出最小的顶点
            int cur = pq.remove().v;

            // 如果取出的结点被处理过 不进行后续操作，进入下一次循环
            if(visited[cur]) continue;

            // 标记当前结点找到一条最短路径
            visited[cur] = true;
            // 从cur顶点 遍历所有相邻顶点 ， 最多获得E条
            for (int w : G.adj(cur)) {
                //判断顶点是否访问过
                if (!visited[w]) {
                    // 判断原点到当前点的距离加上cur这条边的长度是否小于原点到w点更小
                    if (dis[cur]+G.getWeight(cur , w) < dis[w]) {
                        // 更新w点的最短距离
                        dis[w] = dis[cur]+G.getWeight(cur , w);
                        // 这个点加入到优先队列
                        pq.add(new Node(w,dis[w]));
                        //记录路径
                        pre[w] = cur;
                    }
                }
            }
        }
    }

    //用户传来的顶点v是否有路径
    public boolean isConnectedTo(int v) {
        G.validateVertex(v);
        return visited[v];
    }

    // 原点s到顶点v 对应的最短路径的长度
    public int distTo(int v) {
        G.validateVertex(v);
        return dis[v];
    }

    /**
     * 显示最短路径的次序
     * @param t 到达结点
     * @return
     */
    public Iterable<Integer> path(int t) {
        ArrayList<Integer> res = new ArrayList<>();
        if (!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        WeightedGraph g = new WeightedGraph("g.txt");
        DijkstraByPriorityQuene dijkstra = new DijkstraByPriorityQuene(g,0);
        for (int v = 0; v < g.V(); v++) {
            System.out.print(dijkstra.distTo(v) +" ");
        }
        System.out.println();
        System.out.println(dijkstra.path(3));
    }
}
